/*
 * @lc app=leetcode.cn id=84 lang=cpp
 *
 * [84] 柱状图中最大的矩形
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // [6,7,5,2,4,5,9,3], size=7
        // left  :[−1,0,−1,−1,3,4,5,3], guard=-1
        // right :[2,2,3,8,7,7,7,8], guard=8

        // unsorted array
        // search for the first num less than current
        
        // mono stack
        //       top
        // [1, 3, 5]
        // when push 2, pop all instance larger than 2 (3, 5)
        // so it's still increasing
        //    top
        // [1, 2]

        // mono stack just need to cache pos index
        // get height from heights[mono.top()]
        std::stack<int> mono;
        int n = heights.size();

        std::vector<int> left(n);
        std::vector<int> right(n);

        // left -> right
        for (int i=0;i<n;++i){
            while (!mono.empty() && 
                    heights[mono.top()] >= heights[i]) {
                mono.pop();
            }
            left[i] = (mono.empty() ? -1 : mono.top());
            mono.push(i);

            // and ??????
            // how to understand these in compile ~
            // may cause UB ?????
            // empty and than [top()]
            
            // bool useGuardFlag = false;
            // if (mono.empty()){
            //     useGuardFlag = true;
            // }else{
            //     while (heights[mono.top()] >= heights[i]){
            //         mono.pop();
            //         if (mono.empty()){useGuardFlag = true;}
            //     }
            // }
            // left[i] = useGuardFlag ? -1 : mono.top();
            // mono.push(i);
        }

        mono = std::stack<int>();

        // right -> left
        for (int i=n-1;i>=0;--i){
            while (!mono.empty() && 
                    heights[mono.top()] >= heights[i]) {
                mono.pop();
            }
            right[i] = (mono.empty() ? n : mono.top());
            mono.push(i);
        }

        int max = 0;
        for (int i=0;i<n;++i){
            int current = (right[i] - left[i] - 1)*heights[i];
            if (current>max){max=current;}
        }
        return max;
    }
};
// @lc code=end

int main(){
    vector<int> heights{2,1,5,6,2,3};
    Solution test;
    int res = test.largestRectangleArea(heights);
    printf("%d \n", res);
}

class SolutionFool {
public:
    int largestRectangleArea(vector<int>& heights) {
        // <height, length>
        std::map<int, int> rectangularInfo;

        int max = 0;

        rectangularInfo.emplace(heights[0], 1);

        for (int i=1;i<heights.size();++i){
            int height = heights[i];

            auto iter = rectangularInfo.begin();
            while (iter != rectangularInfo.end()){
                if (height >= iter->first){
                    iter->second += 1;
                    ++iter;
                }else{
                    int temp = iter->first * iter->second;
                    if (temp > max){max = temp;}

                    auto check = rectangularInfo.find(height);
                    if (check == rectangularInfo.end()){
                        rectangularInfo.emplace(height, iter->second+1);
                        iter = rectangularInfo.erase(iter);
                    }else{
                        iter = rectangularInfo.erase(iter);
                    }
                }
            }

            if (rectangularInfo.rbegin()->first < height){
                rectangularInfo.emplace(height, 1);
            }
        }

        for (auto& info : rectangularInfo){
            int temp = info.first * info.second;
            if (temp > max){max = temp;}
        }

        return max;
    }
};
